package hash;

import org.junit.Test;

import java.util.*;

/**
 * @author kunkun
 * @className LeetCode_128
 * @Description 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度
 * @date 2025/2/27 15:58
 */
public class LeetCode_128 {

    public int longestConsecutive(int[] nums) {
        return solution_2(nums);
    }

    @Test
    public void test_solution(){
//        int[] nums ={1,0,1,2};
//        int[] nums ={0,3,7,2,5,8,4,6,0,1};
//        int[] nums ={100,4,200,1,3,2};
        int[] nums ={9,1,-3,2,4,8,3,-1,6,-2,-4,7};
        System.out.println(longestConsecutive(nums));
    }

    /**
    * @Description: 方法1：使用排序算法，先排序，在寻找最大长度（缺陷：时间复杂度超过O（n），不符合题目要求）
    * @Author: kunkun
    * @Date:  2025/2/27 16:11
    * @Parameters:
    * @Return
    * @Throws
    */
    public static Integer solution_1(int[] nums){

        //0. 其它情况
        if (nums.length == 0){
            return 0;
        }else if(nums.length == 1){
            return 1;
        }
        //1. 排序
        Arrays.sort(nums);
        //2. 逐个遍历nums
        int maxLength = 1,currentLength = 1 , before = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i]-1==before){
                currentLength++;
                if (currentLength>maxLength){
                    maxLength = currentLength;
                }
            }else if(nums[i]==before){
                ;
            }else{
                currentLength = 1;
            }
            before = nums[i];
        }
        return maxLength;
    }

    /**
    * @Description: 方法2：将nums数组存储至set中，从最小值开始，逐个判断是否在nums中（注意：去除已经计算过的）
    * @Author: kunkun
    * @Date:  2025/2/27 16:21
    * @Parameters:
    * @Return
    * @Throws
    */
    public static Integer solution_2(int[] nums){

        //0. 去重空情况
        if (nums.length==0){
            return 0;
        } else if (nums.length==1) {
            return 1;
        }

        //1. 将nums存入set中
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        //2. 逐个遍历
        int currentLength=1,maxLength=1;
        for (Integer num : set) {
            //2.1 判断，如果num-1在集合内，说明这个数已经被计算过
            if (set.contains(num-1)){
                continue;
            }
            //2.2 逐个判断num后面的数是否在集合中
            int end = num+1;
            currentLength = 1;
            while(set.contains(end)){
                currentLength++;
                end++;
            }
            //2.3 判断是否更新maxLength
            if (currentLength>maxLength){
                maxLength = currentLength;

            }
        }
        return maxLength;
    }

}
